#include <vector>
using namespace std;
#include <set>
#include <algorithm>


// version 1 
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0, right = arr.size() - 1, mid = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            //中点，并不清楚它是在左区间？中间？右区间
            
            if(mid == 0 || arr[mid] < arr[mid + 1]) left = mid + 1; //左区间
            else if(mid == arr.size() - 1 || arr[mid] < arr[mid - 1]) right = mid - 1; //右区间
            else return mid; //山顶
        }
        return 0; //这个就是为了照顾编译器的，随便返回一个就好了！
    }
};

//version 2
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, right = arr.size() - 2; //数组左右端点不可能是答案，掠过
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid - 1] < arr[mid]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};